//
// Created by PC on 2024/5/9.
//


#include <iostream>
#include <vector>
#include "arrUtil.h"

using namespace std;
int part(vector<int> &v, int l, int r)
{
    int le = l-1;
    int cur = v[l];
    for (int i = l; i <= r; ++i)
    {
        if(v[i]<=cur){
            ++le;
            swap(v[i],v[le]);
        }
    }
    swap(v[l],v[le]);
    return le;
}

void quickSort(vector<int> &v, int l, int r)
{
    if(l<r)
    {
        int m = part(v,l,r);
        quickSort(v,l,m-1);
        quickSort(v,m+1,r);
    }
}

int main()
{
    vector<int> arr = {7, 2, 9, 3, 6, 3, 6, 5, 4};
//    cout<<part(arr,0,arr.size()-1)<<endl;
    quickSort(arr,0,arr.size()-1);
    printVector(arr);
    return 0;
}